﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TimDuong
{
    /// <summary>
    /// Lớp thuật toán BFS tìm đường đi ngắn nhất
    /// </summary>
    class BFS
    {
        #region Danh sách biến        
        private int[,] maTran; // Bản đồ
        private Queue<Point> queuePoint = new Queue<Point>();
        private Point lastPoint; // Vị trí cuối

        /// <summary>
        /// Tính vị trí liên thông
        /// </summary>
        private int[] step_X = { -1, 1, 0, 0};
        private int[] step_Y = { 0, 0, -1, 1};

        public int[,] Path = new int[100, 2]; // Lưu thông tin đường đi
        public int Path_index = 0; // Chỉ mục index của Path
        #endregion
        
        public BFS(int[,] _matran, int _x, int _y)
        {
            maTran = _matran;
            queuePoint.Enqueue(new Point(_x, _y, new Point(_x, _y)));
        }

        /// <summary>
        /// Thực hiện tìm đường đi
        /// </summary>
        /// <returns>true nếu tìm được</returns>
        public bool FindPath()
        {
            bool _foud = false;
            while (queuePoint.Count > 0 && _foud == false)
            {
                Point _point_temp = queuePoint.Dequeue();
                int _x = _point_temp.X;
                int _y = _point_temp.Y;                
                for (int i = 0; i < 4; i++)
                {
                    if ((_x + step_X[i] < 10) && (_x + step_X[i] >= 0) && (_y + step_Y[i] < 10) && (_y + step_Y[i] >= 0))
                    {
                        if (Move(_x + step_X[i], _y + step_Y[i], _point_temp))
                        {
                            _foud = true;
                            break;
                        }
                    }
                }
            }
            if (_foud)
                PrintPath();
            return _foud;
        }

        /// <summary>
        /// Kiễm tra vị trí liên thông
        /// </summary>
        /// <param name="_x">tọa độ _x</param>
        /// <param name="_y">tọa độ _y</param>
        /// <param name="_point">nút tọa độ đang xét</param>
        /// <returns>true nếu đã đến đích, false nếu chưa đến</returns>
        private bool Move(int _x,int _y, Point _point)
        {
            if (maTran[_x, _y] == 0)
            {
                AddPoint(_x, _y, _point);                
            } 
            else                
                if (maTran[_x, _y] == 2)
                {
                    lastPoint = new Point(_x, _y, _point);                    
                    return true;
                }
            return false;
        }

        /// <summary>
        /// Tạo nút mới,
        /// Đánh dấu trên bản đồ đã đi qua
        /// </summary>
        /// <param name="_x">tọa độ _x mới</param>
        /// <param name="_y">tọa độ _y mới</param>
        /// <param name="_pre_point">nút liên kết</param>
        private void AddPoint(int _x, int _y, Point _pre_point)
        {            
            queuePoint.Enqueue(new Point(_x, _y, _pre_point));
            maTran[_x, _y] = 1;
        }

        /// <summary>
        /// In đường đi lên mảng Path
        /// </summary>
        private void PrintPath()
        {            
            Point _temp = lastPoint;
            while (!_temp.isRoot())
            {
                Path[Path_index, 0] = _temp.X;
                Path[Path_index, 1] = _temp.Y;
                Path_index++;
                _temp = _temp.Previous;
            }
            Path[Path_index, 0] = _temp.X;
            Path[Path_index, 1] = _temp.Y;
            Path_index++;
        }
    }

    /// <summary>
    /// Lớp định nghĩa nút có tọa độ (X,Y) và nút liên thông
    /// </summary>
    public class Point
    {
        public int X;
        public int Y;        
        public Point Previous;

        public Point(int _x, int _y)
        {
            X = _x;
            Y = _y;            
        }

        public Point(int _x, int _y, Point _pre)
        {
            X = _x;
            Y = _y;
            Previous = _pre;
        }        

        public bool isRoot()
        {
            return (X == Previous.X && Y == Previous.Y);
        }
    }
}
